package offer

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(H) 树的高度，递归调用栈的层次
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
	var dfs func(node *TreeNode) *TreeNode
	dfs = func(node *TreeNode) *TreeNode {
		if node == nil {
			return nil
		}
		node.Left = dfs(node.Left)
		node.Right = dfs(node.Right)
		if node.Left == nil && node.Right == nil && node.Val == 0 {
			return nil
		}
		return node
	}
	return dfs(root)
}
